记 为 毫升泡沫的酒在架子上的瓶数,。
为了方便将二元组视为有序,答案除以 即可。
如果有多个 上面的式子就 GG 了,不过这也很好处理,直接将答案减去/加上 的个数即可。
时间复杂度
#include <cstdio>
#define LL long long
const int MAXN = 5e5;
int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) prime[ ++ prnum ] = i , mu[ i ] = -1;
for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
}
int n , q , a[ MAXN + 5 ] , c[ MAXN + 5 ];
LL Ans;
bool on[ MAXN + 5 ];
LL Calc[ MAXN + 5 ];
// int Calc( int d ) {
// int tmp = 0;
// for( int i = d ; i <= MAXN ; i += d ) tmp += c[ i ];
// return tmp;
// }
void Add( int x ) {
for( int d = 1 ; d * d <= x ; d ++ )
if( x % d == 0 ) {
Ans += mu[ d ] * ( 2 * Calc[ d ] + 1 ) , Calc[ d ] ++;
if( d * d != x ) Ans += mu[ x / d ] * ( 2 * Calc[ x / d ] + 1 ) , Calc[ x / d ] ++;
}
c[ x ] ++;
if( x == 1 ) Ans --;
}
void Del( int x ) {
for( int d = 1 ; d * d <= x ; d ++ )
if( x % d == 0 ) {
Ans -= mu[ d ] * ( 2 * Calc[ d ] - 1 ) , Calc[ d ] --;
if( d * d != x ) Ans -= mu[ x / d ] * ( 2 * Calc[ x / d ] - 1 ) , Calc[ x / d ] --;
}
c[ x ] --;
if( x == 1 ) Ans ++;
}
int main( ) {
sieve();
scanf("%d %d",&n,&q);
for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]);
for( int i = 1 , pos ; i <= q ; i ++ ) {
scanf("%d",&pos);
on[ pos ] ? Del( a[ pos ] ) : Add( a[ pos ] );
on[ pos ] ^= 1;
printf("%lld\n", Ans / 2 );
}
return 0;
}